home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Xconq 7.1.0 / src / xconq-7.1.0 / kernel / mkroads.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-07  |  9.3 KB  |  320 lines  |  [TEXT/R*ch]
  1. /* Road generation for Xconq.
  2.    Copyright (C) 1991, 1992, 1993, 1994, 1995 Stanley T. Shebs.
  3.  
  4. Xconq is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2, or (at your option)
  7. any later version.  See the file COPYING.  */
  8.  
  9. /* A road generation method that connects specified types of units
  10.    and favors specified types of terrain. */
  11.  
  12. /* (should add some favoring of nearby rather than totally random units?) */
  13.  
  14. #include "conq.h"
  15.  
  16. static int unit_sees_other_unit PARAMS ((Unit *unit1, Unit *unit2));
  17. static int road_at PARAMS ((int x, int y));
  18. static int find_adj_inside_area PARAMS ((int x, int y, int *xp, int *yp));
  19. static void lay_road_between PARAMS ((int x1, int y1, int x2, int y2));
  20. static int test_road_segment PARAMS ((int x, int y, int dir));
  21. static int sort_road_segments PARAMS ((int x, int y, int *dirchoices, int numchoices));
  22. static int compare_road_directions PARAMS ((const void *a0, const void *a1));
  23. static int lay_road_segment PARAMS ((int x, int y, int dir, int choice, int numchoices));
  24.  
  25. static int roadtype;
  26.  
  27. static int *doroads;
  28.  
  29. static int xs[NUMDIRS];
  30. static int ys[NUMDIRS];
  31. static int terrs[NUMDIRS];
  32.  
  33. int
  34. make_roads(calls, runs)
  35. int calls, runs;
  36. {
  37.     int doanyroads = FALSE;
  38.     int i, n, t, u1, u2, ex1, ey1, ex2, ey2, iex1, iey1, iex2, iey2, rx, ry;
  39.     Unit *unit1, *unit2;
  40.  
  41.     /* Look for a suitable terrain type. */
  42.     roadtype = NONTTYPE;
  43.     for_all_terrain_types(t) {
  44.     if (t_is_connection(t)
  45.         && !aux_terrain_defined(t)
  46.         && t_subtype_x(t) == 12 /*keyword_value(K_ROAD_X)*/) {
  47.         roadtype = t;
  48.         break;
  49.     }
  50.     }
  51.     if (roadtype == NONTTYPE)
  52.       return FALSE;
  53.     if (doroads == NULL)
  54.       doroads = (int *) xmalloc(numutypes * sizeof(int));
  55.     /* Compute which unit types will have roads. */
  56.     for_all_unit_types(u1)
  57.       doroads[u1] = FALSE;
  58.     for_all_unit_types(u1) {
  59.     for_all_unit_types(u2) {
  60.         if (uu_road_chance(u1, u2) > 0) {
  61.         doroads[u1] = TRUE;
  62.         doanyroads = TRUE;
  63.         break;
  64.         }
  65.     }
  66.     if (u_road_to_edge_chance(u1) > 0) {
  67.         doroads[u1] = TRUE;
  68.         doanyroads = TRUE;
  69.     }
  70.     }
  71.     if (g_edge_road_density() > 0)
  72.       doanyroads = TRUE;
  73.     /* Don't run if road chance always zero. */
  74.     if (!doanyroads)
  75.       return FALSE;
  76.     /* Now we're ready to get down to work. */
  77.     allocate_area_aux_terrain(roadtype);
  78.     announce_lengthy_process("Laying down roads");
  79.     /* (should be able to announce progress by guessing at number of roads) */
  80.     /* Run roads between units. */
  81.     for_all_units(unit1) {
  82.     if (in_play(unit1) && doroads[unit1->type]) {
  83.         for_all_units(unit2) {
  84.         if (unit1 != unit2
  85.             && in_play(unit2)
  86.             && (g_see_all()
  87.             || unit1->side == unit2->side
  88.             || (unit_sees_other_unit(unit1, unit2)
  89.                 && unit_sees_other_unit(unit2, unit1)))
  90.             && probability(uu_road_chance(unit1->type, unit2->type))) {
  91.             lay_road_between(unit1->x, unit1->y, unit2->x, unit2->y);
  92.         }
  93.         }
  94.     }
  95.     }
  96.     /* Run roads from units to the edge of the world. */
  97.     for_all_units(unit1) {
  98.     if (in_play(unit1) && doroads[unit1->type]) {
  99.         if (probability(u_road_to_edge_chance(unit1->type))) {
  100.         random_edge_point(&ex1, &ey1);
  101.         lay_road_between(unit1->x, unit1->y, ex1, ey1);
  102.         }
  103.     }
  104.     }
  105.     /* Run roads that go from one edge to another. */
  106.     if (g_edge_road_density() > 0) {
  107.     n = (g_edge_road_density() * (2 * (area.width + area.height))) / 10000;
  108.     /* Ensure at least one road. */
  109.     n = max(n, 1);
  110.     for (i = 0; i < n; ++i) {
  111.         random_edge_point(&ex1, &ey1);
  112.         find_adj_inside_area(ex1, ey1, &iex1, &iey1);
  113.         random_edge_point(&ex2, &ey2);
  114.         find_adj_inside_area(ex2, ey2, &iex2, &iey2);
  115.         lay_road_between(iex1, iey1, iex2, iey2);
  116.     }
  117.     }
  118.     /* Run spurs from unroaded units to existing roads. */
  119.     for_all_units(unit1) {
  120.     if (in_play(unit1)
  121.         && !road_at(unit1->x, unit1->y)
  122.         && u_spur_chance(unit1->type) > 0
  123.         && u_spur_range(unit1->type) > 0) {
  124.         if (probability(u_spur_chance(unit1->type))) {
  125.         if (search_around(unit1->x, unit1->y, u_spur_range(unit1->type),
  126.                   road_at, &rx, &ry, 1)) {
  127.             lay_road_between(unit1->x, unit1->y, rx, ry);
  128.         }
  129.         }
  130.     }
  131.     }
  132.     finish_lengthy_process();
  133.     return TRUE;
  134. }
  135.  
  136. static int
  137. unit_sees_other_unit(unit1, unit2)
  138. Unit *unit1, *unit2;
  139. {
  140.     int u2 = unit2->type;
  141.     Side *side = unit1->side;
  142.  
  143.     /* Independent units are considered to know about all other units
  144.        (not realistic, but no one will notice, since sides with players
  145.        must also be able to see the indep unit before they will have
  146.        a road going to it) */
  147.     if (indep(unit1))
  148.       return TRUE;
  149.     /* This works sometimes, but views aren't always completely set up yet. */
  150.     if (side->unitview != NULL
  151.     && unit_view(side, unit2->x, unit2->y) != EMPTY)
  152.       return TRUE;
  153.     if (side->terrview != NULL
  154.         && terrain_view(side, unit2->x, unit2->y) != UNSEEN
  155.         && (u_see_always(u2)
  156.             || (indep(unit2) ? u_already_seen_indep(u2) : u_already_seen(u2))))
  157.       return TRUE;
  158.     if (people_sides_defined()
  159.         && people_side_at(unit2->x, unit2->y) == side->id)
  160.       return TRUE;
  161.     return FALSE;
  162. }
  163.  
  164. static int
  165. road_at(x, y)
  166. int x, y;
  167. {
  168.     return aux_terrain_at(x, y, roadtype);
  169. }
  170.  
  171. /* Find an interior point adjacent to this one (presumed but not
  172.    required to be on the edge).  This one just picks the first
  173.    found, which is OK for the road generation usage. */
  174.  
  175. static int
  176. find_adj_inside_area(x, y, xp, yp)
  177. int x, y, *xp, *yp;
  178. {
  179.     int dir, x1, y1;
  180.  
  181.     for_all_directions(dir) {
  182.     if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
  183.         *xp = x1;  *yp = y1;
  184.         return TRUE;
  185.     }
  186.     }
  187.     return FALSE;
  188. }
  189.  
  190. /* Do the whole path. */
  191.  
  192. static void
  193. lay_road_between(x1, y1, x2, y2)
  194. int x1, y1, x2, y2;
  195. {
  196.     apply_to_path(x1, y1, x2, y2, test_road_segment, sort_road_segments, lay_road_segment, FALSE);
  197. }
  198.  
  199. static int
  200. test_road_segment(x, y, dir)
  201. int x, y, dir;
  202. {
  203.     int x1, y1;
  204.  
  205.     if (point_in_dir(x, y, dir, &x1, &y1)) {
  206.     return (tt_road_into_chance(terrain_at(x, y), terrain_at(x1, y1)) > 0);
  207.     }
  208.     return FALSE;
  209. }
  210.  
  211. static int
  212. sort_road_segments(x, y, dirchoices, numchoices)
  213. int x, y, *dirchoices, numchoices;
  214. {
  215.     int i, tmp, i0 = 0, i1 = 1, compar;
  216.  
  217.     if (numchoices > 1) {
  218.     /* Cache direction and terrain data. */
  219.     tmpttype = terrain_at(x, y);
  220.     for (i = 0; i < numchoices; ++i) { 
  221.         point_in_dir(x, y, dirchoices[i], &(xs[i]), &(ys[i]));
  222.         terrs[i] = terrain_at(xs[i], ys[i]);
  223.     }
  224.     if (numchoices == 2) {
  225.         compar = compare_road_directions(&i0, &i1);
  226.         if (compar > 0 || (compar == 0 && flip_coin())) {
  227.         tmp = dirchoices[0];
  228.         dirchoices[0] = dirchoices[1];
  229.         dirchoices[1] = tmp;
  230.         }
  231.     } else if (numchoices > 2) {
  232.         qsort(dirchoices, numchoices, sizeof(int),
  233.           compare_road_directions);
  234.         /* Randomize the top two choices if they're equivalent. */
  235.         if (compare_road_directions(&i0, &i1) == 0 && flip_coin()) {
  236.         tmp = dirchoices[0];
  237.         dirchoices[0] = dirchoices[1];
  238.         dirchoices[1] = tmp;
  239.         }
  240.     }
  241.     }
  242.     return numchoices;
  243. }
  244.  
  245. /* This compares the desirability of two different directions.  This is
  246.    somewhat tricky, because it should return < 0 if i0 designates a BETTER
  247.    direction than i1. */
  248.  
  249. static int
  250. compare_road_directions(a0, a1)
  251. CONST void *a0, *a1;
  252. {
  253.     int i0, i1, t0, t1, tmp0, tmp1;
  254.     Unit *unit;
  255.  
  256.     i0 = *((int *) a0);  i1 = *((int *) a1);
  257.     t0 = terrs[i0];  t1 = terrs[i1];
  258.     /* Prefer the direction that already has a road. */
  259.     tmp0 = (aux_terrain_at(xs[i0], ys[i0], roadtype) ? 1 : 0);
  260.     tmp1 = (aux_terrain_at(xs[i1], ys[i1], roadtype) ? 1 : 0);
  261.     if (tmp0 != tmp1)
  262.       return (tmp1 - tmp0);
  263.     /* Prefer the direction that already has a road-connected unit. */
  264.     tmp0 = tmp1 = 0;
  265.     for_all_stack(xs[i0], ys[i0], unit) {
  266.     if (doroads[unit->type]) {
  267.         tmp0 = 1;
  268.         break;
  269.     }
  270.     }
  271.     for_all_stack(xs[i1], ys[i1], unit) {
  272.     if (doroads[unit->type]) {
  273.         tmp1 = 1;
  274.         break;
  275.     }
  276.     }
  277.     if (tmp0 != tmp1)
  278.       return (tmp1 - tmp0);
  279.     /* Prefer the direction whose terrain is more favorable for a road. */
  280.     return (tt_road_into_chance(tmpttype, t1) - tt_road_into_chance(tmpttype, t0));
  281. }
  282.  
  283. /* Lay down a single bit of road, tending to choose directions with more
  284.    favorable underlying terrain and merging with already-existing roads. */
  285.  
  286. static int
  287. lay_road_segment(x, y, d, choice, numchoices)
  288. int x, y, d, choice, numchoices;
  289. {
  290.     int x1, y1, roadchance, foundroad = FALSE, foundunit = FALSE;
  291.     Unit *unit;
  292.  
  293.     if (interior_point_in_dir(x, y, d, &x1, &y1)) {
  294.     /* See if any road already in the other end of this conn. */
  295.     if (aux_terrain_at(x1, y1, roadtype))
  296.       foundroad = TRUE;
  297.     /* See if any road-connected units there. */
  298.     for_all_stack(x1, y1, unit) {
  299.         if (doroads[unit->type]) {
  300.         foundunit = TRUE;
  301.         break;
  302.         }
  303.     }
  304.         roadchance = tt_road_into_chance(terrain_at(x, y), terrain_at(x1, y1));
  305.         if (roadchance > 0) {
  306.             if (probability(roadchance) || foundroad || foundunit) {
  307.         set_connection_at(x, y, d, roadtype, TRUE);
  308.         /* Return whether to keep going or stop because of shared road. */
  309.         /* Note that stopping at a road-connected unit is not desirable,
  310.            because we know (foundroad being false), that it does not already
  311.            have a road running to it, and so we need to finish getting this
  312.            one to where it is supposed to go. */
  313.         return (foundroad ? -1 : 1);
  314.         }
  315.     }
  316.     }
  317.     /* Try next. */
  318.     return 0;
  319. }
  320.